#include <string.h>
#include <iostream>
using namespace std;
// An implementation of a Disjoint Set Tree Class

// Constructor
template <typename T>
DisjointSet<T>::DisjointSet(T contents) {
  data = contents;
  parent = NULL; //Initially in own tree with no root
  rank = 0; // Own tree has 1 element and rank 0 (no levels)
}

// Destructor
template <typename T>
DisjointSet<T>::~DisjointSet() {
  // Do nothing
}

// Get the contained data
template <typename T>
T DisjointSet<T>::getData() {
  return this->data;
}



// Print out the tree for debugging
template <typename T>
void DisjointSet<T>::DebugPrint(){
  DisjointSet<T> * current = this;
  while (current != NULL) {
    cout << "( " <<  current->data << ") --> ";
    current = current->parent;
  }
  cout << "--|" << endl;
}


// Find the root of the tree that contains the node of interest
template <typename T>
DisjointSet<T> * DisjointSet<T>::Find(){
  if (this->parent != NULL) { // If there is a parent
    this->parent = parent->Find(); // Set the parent to the parent's parent
    // This flattens the tree to make faster accesses later
    return parent;
  }
  return this;
}

// Check if two nodes are in the same tree
template <typename T>
bool DisjointSet<T>::sameSet(DisjointSet<T> * other) {
  return (this->Find() == other->Find());
}

// Join two groups of nodes together
template <typename T>
int DisjointSet<T>::Union(DisjointSet<T> * other) {
  DisjointSet<T> * root1 = this->Find();
  DisjointSet<T> * root2 = other->Find();
  
  if (root1 == root2){ // Trees in same set
    return 0;
  }
  
  // Append the smaller tree to the larger one
  if (root1->rank < root2->rank) {
    root1->parent = root2;
  }
  else if (root1->rank > root2->rank) {
    root2->parent = root1;
  }
  else { // Trees same height
    root1->parent = root2;
    root2 ->rank += 1;

  }
  return 1;
}


